class Solution(object):
    def combinationSum4(self, nums, target):
        dp = [0] * (target+1)
        nums.sort()
        for num in nums:
            if num<len(dp): dp[num]=1
            else: break
        for i in range(len(dp)):
            if dp[i]!=0:
                for num in nums:
                    next = i+num
                    if next<len(dp): dp[next] += dp[i]
                    else: break
        return dp[-1]
        
print(Solution().combinationSum4([1,2,3],4))